package leetcode.weekly.week343;

import java.util.Arrays;

//Solution3Test
public class Solution3 {
	private long f(long a, long b, long c, long d) {
		return Math.abs(a - c) + Math.abs(b - d);
	}

	public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
		int sx = start[0], sy = start[1];
		int tx = target[0], ty = target[1];
		int n = specialRoads.length;
		long[] dp = new long[n];
		Arrays.fill(dp, Integer.MAX_VALUE);
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				long x = specialRoads[i][0], y = specialRoads[i][1], o = specialRoads[i][2], p = specialRoads[i][3],
						c = specialRoads[i][4];
				dp[i] = Math.min(dp[i], Math.min(f(o, p, tx, ty) + c, f(x, y, tx, ty)));
				for (int j = 0; j < n; j++) {
					long u = specialRoads[j][0], v = specialRoads[j][1];
					dp[i] = Math.min(dp[i], Math.min(dp[j] + c + f(o, p, u, v),dp[j] +  f(x, y, u, v)));
				}
			}
		}
		long ans = f(sx, sy, tx, ty);
		for (int i = 0; i < n; i++) {
			int x = specialRoads[i][0], y = specialRoads[i][1], o = specialRoads[i][2], p = specialRoads[i][3];
			ans = Math.min(ans, f(sx, sy, x, y) + dp[i]);
		}
		return (int) ans;
	}

}
